function sum(arr) {
  if (arr.length <= 1) {
    return 0
  }
  let index = 0
  mergeSort(arr)
  function mergeSort(arr) {
    const length = arr.length;
    if (length === 1) { //递归算法的停止条件，即为判断数组长度是否为1
      return arr;
    }
    const mid = Math.floor(length / 2);

    const left = arr.slice(0, mid);
    const right = arr.slice(mid, length);
    return merge(mergeSort(left), mergeSort(right));
  }
  function merge(left, right) {
    const result = [];
    let il = 0;
    let ir = 0;
    //left, right本身肯定都是从小到大排好序的
    while (il < left.length && ir < right.length) {
      if (left[il] < right[ir]) {
        result.push(left[il]);
        il++;
      } else {
        index = index + (left.length - il)
        result.push(right[ir]);
        ir++;
      }

    }

    //不可能同时存在left和right都有剩余项的情况, 要么left要么right有剩余项, 把剩余项加进来即可
    while (il < left.length) {
      result.push(left[il]);
      il++;
    }
    while (ir < right.length) {
      result.push(right[ir]);
      ir++;
    }
    return result;
  }
  return index
}


console.log(sum([1,2,3,4,5,6,7,0]))